#
# @lc app=leetcode.cn id=2909 lang=python3
#
# [2909] 元素和最小的山形三元组 II
#

# @lc code=start
from cmath import inf
from typing import List

class Solution:
    def minimumSum(self, nums: List[int]) -> int:
        n = len(nums)
        ans = inf
        suf =[0] * n    # suf[i]记录了 i-n-1之间的最小值
        suf[n-1] = nums[n-1]
        pre_min = nums[0] # 维护 i位置之前的最小值
        for i in range(n-2, 1,-1):
            suf[i] = min(suf[i+1],nums[i])
        for i in range(1,n-1):
            if pre_min < nums[i] > suf[i+1]: # 可以构成山形数组
                ans = min(ans,pre_min + nums[i] + suf[i+1])
            pre_min = min(pre_min,nums[i])
        return ans if ans < inf else -1
# @lc code=end

